package com.ddshuai.easy;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 合并两个已排序的链表，并将其作为一个新列表返回。新列表应该通过拼接前两个列表的节点来完成。
 *
 * @author admin
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 */
public class MergeTwoList {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //简单的逻辑来一遍 将数据放到一个集合里 排序后重组
        List<ListNode> listNodes = buildList(l1,l2);
        ListNode root = null;
        ListNode currentNode = null;
        for (ListNode listNode : listNodes) {
            if (root == null){
                root = listNode;
                currentNode = listNode;
            }else {
                currentNode.setNext(listNode);
                currentNode = listNode;
            }
        }
        return root;
    }

    private static List<ListNode> buildList(ListNode l1, ListNode l2) {
       List<ListNode> listNodes = new ArrayList<>();
       if (l1 == null || l2 == null){
           return listNodes;
       }
       getList(l1,listNodes);
       getList(l2,listNodes);

       listNodes.sort(Comparator.comparingInt(ListNode::getVal));

       return listNodes;

    }

    private static void getList(ListNode l1,List<ListNode> listNodes) {
        if (l1 != null){
            listNodes.add(l1);
            if (l1.getNext() != null){
                getList(l1.getNext(),listNodes);
            }
        }

    }


   static class ListNode implements Comparable<Integer> {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public ListNode getNext() {
            return next;
        }

        public void setNext(ListNode next) {
            this.next = next;
        }

       @Override
       public String toString() {
           return "ListNode{" +
                   "val=" + val +
                   ", next=" + next +
                   '}';
       }

       @Override
        public int compareTo(Integer o) {
            return this.val - o;
        }
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        listNode1.setNext(listNode3);
        listNode3.setNext(listNode2);

        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(6);
        listNode4.setNext(listNode5);
        listNode5.setNext(listNode6);


        System.out.println( mergeTwoLists(listNode1,listNode4));
    }

}
